//timer management, use timer wheel
// Created: Daly 2012-4-6


#include "xnt_timer.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>
#include <assert.h>

extern int g_tick_interval;  //define in xnt_event.c  1000/frame_rate

static unsigned int _ticknow = 0;    //how many ticks from start
static int g_timer_init = 0;
static int g_timer_handle = 1;    //int is enough
static unsigned long long _time_start = 0;  //to calculate time pass from start
static unsigned long long _time_last = 0;  //last tick time
static unsigned long long _time_now = 0;  //unit: millisec
static unsigned long long _time_slap = 0;   //next timer trigger

#define TIMER_TABLE_SIZE 1000

//search by handle-id 
struct timer_entry* _timer_table[TIMER_TABLE_SIZE];

//timer wheel implementation
//reference: 
//	George Varghese , Tony Lauck. Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility (1996)
//	example: linux kernel timer, ACE library timer 

#define SLOT_PER_WHEEL 1024
#define TOTAL_WHEEL 3
//use 3 timer wheel. it's enough to run serverl years without shutdown!
//enought for 1024^3 ms
static struct timer_wheel_entry* _timer_wheel[TOTAL_WHEEL][SLOT_PER_WHEEL];
static int _slot_now[TOTAL_WHEEL];  //corresponding slot according timetick now

//entry allocation pool
// 25000 is enough because when timeout, timer_entry will be free
// in case is not enough, use malloc()
#define TIMER_ENTRY_POOL_SIZE 25000
static struct timer_entry _entry_pool[ TIMER_ENTRY_POOL_SIZE ];
static struct timer_wheel_entry _wheel_pool[ TIMER_ENTRY_POOL_SIZE ]; 
//use stack to record free entry
static unsigned short _entry_free_stack[TIMER_ENTRY_POOL_SIZE];
static unsigned short _wheel_free_stack[TIMER_ENTRY_POOL_SIZE];

static unsigned short _entry_sp = 0;
static unsigned short _wheel_sp = 0;

//mem allocate
timer_entry* alloc_entry()
{
	int idx;
	struct timer_entry *p = NULL;
	if (_entry_sp < TIMER_ENTRY_POOL_SIZE -1) {
		idx = _entry_free_stack[_entry_sp];
		_entry_sp++;	
		p = _entry_pool + idx;
	} else {
		//stack is full!! malloc a node(not a common situation)
		p = (timer_entry*)malloc(sizeof(timer_entry));
	}

	p->handle = 0;
	p->func = NULL;
	p->next = NULL;
	return p;
}

void free_entry(struct timer_entry *p)
{
	int idx;
	p->func = NULL;
	p->handle = 0;
	p->next = NULL;
	idx = p - _entry_pool;
	if (idx >= 0 && idx < TIMER_ENTRY_POOL_SIZE) {
		//alloc by pool
		if (_entry_sp > 0) _entry_sp--;
		_entry_free_stack[_entry_sp] = idx;
	} else {
		//alloc by malloc
		free(p);
	}
}

struct timer_wheel_entry* alloc_wheel_entry()
{
	int idx;
	struct timer_wheel_entry *p = NULL;
	if (_wheel_sp < TIMER_ENTRY_POOL_SIZE -1) {
		idx = _wheel_free_stack[_wheel_sp];
		_wheel_sp++;	
		p = _wheel_pool + idx;
	} else {
		//stack is full!! malloc a node(not a common situation)
		p = (timer_wheel_entry*)malloc(sizeof(timer_wheel_entry));
	}

	p->handle = 0;
	p->next = NULL;

	return p;
}

void free_wheel_entry(struct timer_wheel_entry *p)
{
	int idx;
	p->handle = 0;
	p->next = NULL;	
	idx = p - _wheel_pool;
	if (idx >= 0 && idx < TIMER_ENTRY_POOL_SIZE) {
		//alloc by pool
		if (_wheel_sp > 0) _wheel_sp--;
		_wheel_free_stack[_wheel_sp] = idx;
	} else {
		//alloc by malloc
		free(p);
	}

}

//find timer entry in hash table
static timer_entry* find_timer_entry(int handle)
{
	struct timer_entry *p = _timer_table[handle % TIMER_TABLE_SIZE];
	while(p != NULL) {
		if (p->handle == handle) break;		
		p = p->next;
	}
	return p;
}

//del it from hash table
static int del_timer_entry(int handle_id)
{
	struct timer_entry *p, *q;
	int target_tick = -1;
	//del table entry
	p = _timer_table[handle_id % TIMER_TABLE_SIZE];
	if (p->handle == handle_id) {
		_timer_table[handle_id % TIMER_TABLE_SIZE] = p->next;
		target_tick = p->trigger_tick;
		free_entry(p);
	} else {
		q = p->next;
		while(q != NULL) {
			if (q->handle == handle_id) {
				p->next = q->next;	
				target_tick = q->trigger_tick;
				free_entry(q);
				break;		
			}
			p = q;
			q = p->next;
		}
	}

	return target_tick;
}

//push to hashtable
static void push_timer_entry(timer_entry *entry)
{
	struct timer_entry *e = _timer_table[entry->handle % TIMER_TABLE_SIZE];
	entry->next = e;
	_timer_table[entry->handle % TIMER_TABLE_SIZE] = entry;
}

//tick to wheel slot
//@return tick   tick to slot[3]
//@return int    which wheel
static int _tick_to_slot(unsigned int tick, int* slot)
{
	slot[0] = tick % SLOT_PER_WHEEL;	
	tick /= SLOT_PER_WHEEL;
	slot[1] = tick % SLOT_PER_WHEEL;
	slot[2] = tick / SLOT_PER_WHEEL;
	if (slot[2] > _slot_now[2]) return 2;
	else if (slot[1] > _slot_now[1]) return 1;
	else return 0;
}

//timer wheel. 3 level:
//  1000() -- 100(1000s) -- 100 step(10s)

int xnt_add_timer(xnt_timer_proc timeout_cb, int timeout)
{
	int slot[3];
	int wheel;
	struct timer_entry *entry;
	struct timer_wheel_entry *p_wheel;
	if (!g_timer_init) return -1;

	entry = alloc_entry();
	p_wheel = alloc_wheel_entry();
	entry->func = timeout_cb;
	if (timeout > g_tick_interval) {
		entry->trigger_tick = _ticknow + (unsigned int)timeout / g_tick_interval;
	} else {
		entry->trigger_tick = _ticknow + 1;
	}
	g_timer_handle++;
	if (g_timer_handle <= 0) g_timer_handle = 1;  //roll to start	
	entry->handle = g_timer_handle;
	push_timer_entry(entry);	

	//add to wheel
	p_wheel->handle = g_timer_handle;
	wheel = _tick_to_slot(entry->trigger_tick, slot);
	p_wheel->next = _timer_wheel[wheel][slot[wheel]];
	_timer_wheel[wheel][slot[wheel]] = p_wheel;
	return entry->handle;
}

int xnt_del_timer(int handle_id)
{
	struct timer_wheel_entry *pw, *qw;
	int target_tick;	
	int slot[3];
	int wheel;

	if (!g_timer_init) return -1;
	target_tick = del_timer_entry(handle_id);	
	if (target_tick == -1) return -1;
	//del timer wheel
	wheel = _tick_to_slot(target_tick, slot);
	pw = _timer_wheel[wheel][slot[wheel]];
	if (pw->handle == handle_id) {
		_timer_wheel[wheel][slot[wheel]] = pw->next;
		free_wheel_entry(pw);
	} else {
		qw = pw->next;
		while(qw != NULL) {
			if (qw->handle == handle_id) {
				pw->next = qw->next;	
				free_wheel_entry(qw);
				break;		
			}
			pw = qw;
			qw = pw->next;
		}
	}	
	return 0;
}

//update timer wheel link list when one round end
static void _move_wheel(int from_slot, int which)
{
	int target_slot[3];
	int target;
	struct timer_wheel_entry *p, *q, *head;
	struct timer_entry *entry;  //target slot

	assert(which > 0 && which < TOTAL_WHEEL);
	p = _timer_wheel[which][from_slot];
	while(p != NULL) {
		q = p->next;
		entry = find_timer_entry(p->handle);
		target = _tick_to_slot(entry->trigger_tick, target_slot);		

		//insert to table
		head = _timer_wheel[target][target_slot[target]];	
		p->next = head;		
		_timer_wheel[target][target_slot[target]] = p;
		p = q;	
	}
	_timer_wheel[which][from_slot] = NULL;
}

void process_tick()
{
	struct timer_wheel_entry *p, *q;
	struct timer_entry *entry;
	_ticknow++;
	_slot_now[0]++;
	//update wheel
	if (_slot_now[0] >= SLOT_PER_WHEEL) {
		_slot_now[0] = 0;
		_slot_now[1]++;
		if (_slot_now[1] >= SLOT_PER_WHEEL) {
			_slot_now[1] = 0;
			_slot_now[2]++;
			assert(_slot_now[2] < SLOT_PER_WHEEL);
			_move_wheel(_slot_now[2], 2);
		} 

		_move_wheel(_slot_now[1], 1);  
	}

	//run slot
	
	p = _timer_wheel[0][_slot_now[0]];

	if (p == NULL) return;

	while (p != NULL) {
		q = p->next;
		//warning: the callback function may delete self!		
		entry = find_timer_entry(p->handle);
		if (entry != NULL) {
			entry->func(entry->handle);
		}
		p = q;
	}	
	//delete all entry
	p = _timer_wheel[0][_slot_now[0]];
	while (p != NULL) {
		q = p->next;
		free_wheel_entry(p);
		p = q;
	}
	_timer_wheel[0][_slot_now[0]] = NULL;
}

void xnt_timer_routine()
{
	struct timeval tv;
	
	if (!g_timer_init) return;

	gettimeofday(&tv, NULL);
	_time_last = _time_now;
	_time_now = tv.tv_sec * 1000 + (tv.tv_usec / 1000);
	if (_time_start == 0) {
		//first trig
		_time_start = _time_now;
	}	
	if (_time_now < _time_slap || _time_now > _time_slap + 1000*60) 
	{
		_time_slap = _time_now;
	} 
	while(_time_now > _time_slap) {
		_time_slap += g_tick_interval;
		process_tick();
	}
}

int xnt_get_timepass()
{
	struct timeval tv;
	gettimeofday(&tv, NULL);
	if (_time_start == 0) {
		_time_start = tv.tv_sec * 1000 + (tv.tv_usec / 1000);
	}
	_time_now = tv.tv_sec * 1000 + (tv.tv_usec / 1000);
	return _time_now - _time_start;
}

void timer_table_init()
{
	int i,j;
	for(i=0; i<TIMER_TABLE_SIZE; i++) {
		_timer_table[i] = NULL;
	}	
	for(i=0; i<TOTAL_WHEEL; i++) {
		for(j=0; j<SLOT_PER_WHEEL; j++) 
		{
			_timer_wheel[i][j] = NULL;
		}
	}
	for(i=0; i<TIMER_ENTRY_POOL_SIZE; i++) {
		_entry_free_stack[i] = i;
		_wheel_free_stack[i] = i;
	}
	g_timer_init = 1;

}
